Product Code Database
The Kemeny method is an electoral system that uses ranked ballots and pairwise comparison counts to identify the most popular choices in an election. It is a Condorcet method because if there is a Condorcet winner, it will always be ranked as the most popular choice.
This method assigns a score for each possible sequence, where each sequence considers which choice might be most popular, which choice might be second-most popular, which choice might be third-most popular, and so on down to which choice might be least-popular. The sequence that has the highest score is the winning sequence, and the first choice in the winning sequence is the most popular choice. (As explained below, ties can occur at any ranking level.)
The Kemeny method is also known as the Kemeny-Young rule, VoteFair popularity ranking, the maximum likelihood method, and the median relation.
Kemeny calculations are usually done in two steps. The first step is to create a matrix or table that counts pairwise voter preferences. The second step is to test all possible total order, calculate a score for each such ranking, and compare the scores. Each ranking score equals the sum of the pairwise counts that apply to that ranking.
The ranking that has the largest score is identified as the overall ranking. (If more than one ranking has the same largest score, all these possible rankings are tied, and typically the overall ranking involves one or more ties.)
Another way to view the ordering is that it is the one which minimizes the sum of the Kendall tau distances (bubble sort distance) to the voters' lists.
In order to demonstrate how an individual preference order is converted into a tally table, it is worth considering the following example. Suppose that a single voter has a choice among four candidates (i.e. Elliot, Meredith, Roland, and Selden) and has the following preference order:
| First | Elliot |
| Second | Roland |
| Third | Meredith or Selden (equal preference) |
These preferences can be expressed in a tally table. A tally table, which arranges all the pairwise counts in three columns, is useful for counting (tallying) ballot preferences and calculating ranking scores. The center column tracks when a voter indicates more than one choice at the same preference level. The above preference order can be expressed as the following tally table:
| X = Selden Y = Meredith | 0 | +1 vote | 0 |
| X = Selden Y = Elliot | 0 | 0 | +1 vote |
| X = Selden Y = Roland | 0 | 0 | +1 vote |
| X = Meredith Y = Elliot | 0 | 0 | +1 vote |
| X = Meredith Y = Roland | 0 | 0 | +1 vote |
| X = Elliot Y = Roland | +1 vote | 0 | 0 |
Now suppose that multiple voters had voted on those four candidates. After all ballots have been counted, the same type of tally table can be used to summarize all the preferences of all the voters. Here is an example for a case that has 100 voters:
| X = Selden Y = Meredith | 50 | 10 | 40 |
| X = Selden Y = Elliot | 40 | 0 | 60 |
| X = Selden Y = Roland | 40 | 0 | 60 |
| X = Meredith Y = Elliot | 40 | 0 | 60 |
| X = Meredith Y = Roland | 30 | 0 | 70 |
| X = Elliot Y = Roland | 30 | 0 | 70 |
The sum of the counts in each row must equal the total number of votes.
After the tally table has been completed, each possible ranking of choices is examined in turn, and its ranking score is calculated by adding the appropriate number from each row of the tally table. For example, the possible ranking:
If there are cycles or ties, more than one possible ranking can have the same largest score. Cycles are resolved by producing a single overall ranking where some of the choices are tied.
| ... over Roland | ... over Elliot | ... over Selden | ... over Meredith | |
| Prefer Roland ... | - | 70 | 60 | 70 |
| Prefer Elliot ... | 30 | - | 60 | 60 |
| Prefer Selden ... | 40 | 40 | - | 50 |
| Prefer Meredith ... | 30 | 40 | 40 | - |
In this summary matrix, the largest ranking score equals the sum of the counts in the upper-right, triangular half of the matrix (shown here in bold, with a green background). No other possible ranking can have a summary matrix that yields a higher sum of numbers in the upper-right, triangular half. (If it did, that would be the overall ranking.)
In this summary matrix, the sum of the numbers in the lower-left, triangular half of the matrix (shown here with a red background) are a minimum. The academic papers by John Kemeny and Peyton Young refer to finding this minimum sum, which is called the Kemeny score, and which is based on how many voters oppose (rather than support) each pairwise order:
| Kemeny | Roland |
| Condorcet method | Roland |
| Instant runoff voting | Elliot or Selden (depending on how the second-round tie is handled) |
| Plurality | Selden |
| ... over Memphis | ... over Nashville | ... over Chattanooga | ... over Knoxville | |
| 42% | ||||
| 68% | ||||
| 83% | ||||
| - |
The Kemeny method arranges the pairwise comparison counts in the following tally table:
| X = Memphis Y = Nashville | 42% | 0 | 58% |
| X = Memphis Y = Chattanooga | 42% | 0 | 58% |
| X = Memphis Y = Knoxville | 42% | 0 | 58% |
| X = Nashville Y = Chattanooga | 68% | 0 | 32% |
| X = Nashville Y = Knoxville | 68% | 0 | 32% |
| X = Chattanooga Y = Knoxville | 83% | 0 | 17% |
The ranking score for the possible ranking of Memphis first, Nashville second, Chattanooga third, and Knoxville fourth equals (the unit-less number) 345, which is the sum of the following annotated numbers.
This table lists all the ranking scores:
| 345 |
| 279 |
| 309 |
| 273 |
| 243 |
| 207 |
| 361 |
| 295 |
| 377 |
| 393 |
| 311 |
| 327 |
| 325 |
| 289 |
| 341 |
| 357 |
| 305 |
| 321 |
| 259 |
| 223 |
| 275 |
| 291 |
| 239 |
| 255 |
The largest ranking score is 393, and this score is associated with the following possible ranking, so this ranking is also the overall ranking:
| First | Nashville |
| Second | Chattanooga |
| Third | Knoxville |
| Fourth | Memphis |
If a single winner is needed, the first choice, Nashville, is chosen. (In this example Nashville is the Condorcet winner.)
The summary matrix below arranges the pairwise counts in order from most popular (top and left) to least popular (bottom and right):
| ... over Nashville ... | ... over Chattanooga ... | ... over Knoxville ... | ... over Memphis ... | |
| Prefer Nashville ... | - | 68% | 68% | 58% |
| Prefer Chattanooga ... | 32% | - | 83% | 58% |
| Prefer Knoxville ... | 32% | 17% | - | 58% |
| Prefer Memphis ... | 42% | 42% | 42% | - |
In this arrangement the largest ranking score (393) equals the sum of the counts in bold, which are in the upper-right, triangular half of the matrix (with a green background).
A tie can occur at any preference level. Except in some cases where circular ambiguities are involved, the Kemeny method only produces a tie at a preference level when the number of voters with one preference exactly matches the number of voters with the opposite preference.
It has been reportedVincent Conitzer, Andrew Davenport, and Jayant Kalagnanam, " Improved bounds for computing Kemeny rankings" (2006). that calculation methods based on integer programming sometimes allowed the computation of full rankings for votes on as many as 40 candidates in seconds. However, certain 40-candidate 5-voter Kemeny elections generated at random were not solvable on a 3 GHz Pentium computer in a useful time bound in 2006.
The Kemeny method can be formulated as an instance of a more abstract problem, of finding weighted feedback arc sets in . As such, many methods for the computation of feedback arc sets can be applied to this problem, including a variant of the Held–Karp algorithm that can compute the Kemeny–Young ranking of candidates in time , significantly faster for many candidates than the factorial time of testing all rankings. There exists a polynomial-time approximation scheme for computing a Kemeny ranking,"How to Rank with Few Errors"
In 1978, Peyton Young and Arthur Levenglick axiomatically characterized the method, showing that it is the unique neutral method satisfying consistency and the so-called quasi-Condorcet criterion.H. P. Young and A. Levenglick, "", SIAM Journal on Applied Mathematics 35, no. 2 (1978), pp. 285–300. It can also be characterized using consistency and a monotonicity property. In other papers,H. P. Young, "Condorcet's Theory of Voting", American Political Science Review 82, no. 2 (1988), pp. 1231–1244.
H. P. Young, "Optimal ranking and choice from pairwise comparisons", in Information pooling and group decision making edited by B. Grofman and G. Owen (1986), JAI Press, pp. 113–122.
H. P. Young, "Optimal Voting Rules", Journal of Economic Perspectives 9, no.1 (1995), pp. 51–64.
H. P. Young, "Group choice and individual judgements", Chapter 9 of Perspectives on public choice: a handbook, edited by Dennis Mueller (1997) Cambridge UP., pp.181 –200.
Young adopted an Epistemology approach to preference aggregation: he supposed that there was an objectively 'correct', but unknown preference order over the alternatives, and voters receive noisy signals of this true preference order (cf. Condorcet's jury theorem.) Using a simple probabilistic model for these noisy signals, Young showed that the Kemeny method was the maximum likelihood estimator of the true preference order. Young further argues that Condorcet himself was aware of the Kemeny rule and its maximum-likelihood interpretation, but was unable to clearly express his ideas.
In the papers by John Kemeny and Peyton Young, the Kemeny scores use counts of how many voters oppose, rather than support, each pairwise preference, but the smallest such score identifies the same overall ranking.
Since 1991 the method has been promoted under the name "VoteFair popularity ranking" by Richard Fobes.Richard Fobes, "The Creative Problem Solver's Toolbox", (), 1993, pp. 223–225.
/ref> and there also exists a parameterized subexponential-time algorithm with running time O*(2O()) for computing such a ranking.Karpinski, M. and Schudy, W., "Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament", in: Cheong, O., Chwa, K.-Y., and Park, K. (Eds.): ISAAC 2010, Part I, LNCS 6506, pp. 3-14.
History
The Kemeny method was developed by John Kemeny in 1959.John Kemeny, "Mathematics without numbers", Daedalus 88 (1959), pp. 577–591.
Comparison table
The following table compares the Kemeny method with other single-winner election methods:
Notes
External links
|
|
